class Parser 

  def pullSLiterals(string) #method used to remove all string literals, save them in an array, and replace them with a set string that will not interfere with parsing
    pattern = /"([^"\\]|\\.)*"/
    replace = "***STRING-LITERAL***"
    literals = []
    string.gsub(pattern) do |occurence|
      literals << occurence
    end
    string = string.gsub(pattern, replace)
    return [string, literals]
  end
  
  def tokenize(string) #method used split program into tokens by adding spaces arround '('s and calling string.split(' ')
    numOpen = string.count("(")
    numClose = string.count(")")
    numMissing = 0
    if numOpen > numClose
      numMissing = numOpen - numClose
      raise RuntimeError, "#{numMissing} missing close parenthasees"
    elsif numClose > numOpen
      numMissing = numClose - numOpen
      raise RuntimeError, "#{numMissing} extra close parenthasees"
    elsif numClose == numOpen
      string = string.gsub("(", " ( ")
      string = string.gsub(")", " ) ")
      tokens = string.split(" ")
      return tokens
    end
  end
  
  def replaceSLiterals(tokens, literals) #method used to restore string literals in our tokens array now that we dont have to worry about special cases
    return tokens.map do |token|
      if token == "***STRING-LITERAL***"
        literals.shift
      else
        token
      end
    end
  end

  def isMatch?(string, pattern) #check if type is a match, returns false if no, true if yes
    match = string.match(pattern)
    return false unless match
    match[0].length == string.length
  end

  def isSymbol?(string) #return true if string is anything other than parenthasees, quotes, or commas
    return isMatch?(string, /[^\"\'\,\(\)]+/)
  end

  def isInteger?(string) #return true if string is made of any number of numerals optionally preceded by a + or -
    return isMatch?(string, /[\-\+]?[0-9]+/)
  end

  def isFloat?(string)
    return isMatch?(string, /[-+]?[0-9]*\.?[0-9]+/)
  end

  def isString?(string) #return true if string is text surrounded by quotes
    return isMatch?(string, /"([^"\\]|\\.)*"/)
  end

  def isComma?(string)
    return isMatch?(string, /.*,.*/)
  end

  def convertTokens(tokens)
    convertedTokens = []
    tokens.each do |token|
      convertedTokens << "(" and next if token == "("
      convertedTokens << ")" and next if token == ")"
      convertedTokens << token.to_i and next if isInteger?(token)
      convertedTokens << token.to_f and next if isFloat?(token)
      convertedTokens << token.to_sym and next if isSymbol?(token)
      convertedTokens << eval(token) and next if isString?(token)
      convertedTokens << token and next if isComma?(token)
      raise Exception, "Unrecognized token: #{token}"
    end
    return convertedTokens
  end

  def formStructure(tokens, offset = 0)
    structure = []
    while offset < tokens.length do
      if tokens[offset] == "("
        offset, tempArray = formStructure(tokens, offset + 1)
        structure << tempArray
      elsif tokens[offset] == ")"
        break
      else
        structure << tokens[offset]
      end
      offset += 1
    end
    return [offset, structure]
  end
  
  def parse(string)
    string, literals = pullSLiterals(string)
    tokens = tokenize(string)
    tokens = replaceSLiterals(tokens, literals)
    tokens = convertTokens(tokens)
    structure = formStructure(tokens)[1]
    return structure
  end

  def convertLiterals(data)
    return recursiveMap(data) do |x|
      case x
      when nil then []
      when true then :"#t"
      when false then :"#f"
      else x
      end
    end
  end
      
      # Convert a set of nested arrays back into an S-Expression
  def toToken(data)
    data = convertLiterals(data)
    if(data.is_a?(Array))
      mapped = data.map do |item|
        if(item.is_a?(Array))
          toToken(item)
        else
          item.to_s
        end
      end
      "(" + mapped.join(" ") + ")"
    elsif (data.is_a?(Hash))
      mapped = data.map do |key, value|
        key = toToken(key)
        value = toToken(value)
        key + "=>" + value
      end
      "(" + mapped.join(" ") + ")"
    else
      data.to_s
    end
  end
    
  private
  
  def recursiveMap(data, &block)
    if(data.is_a?(Array))
      return data.map do |x|
        if(x.is_a?(Array))
          recursiveMap(x, &block)
        else
          block.call(x)
        end
      end
    else
      block.call(data)
    end
  end
end

